package now_coder.greedy.ncs;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;

public class NC147 {

    public int minmumNumberOfHost (int n, int[][] startEnd) {
        if(n <= 1){
            return n;
        }
        // 首先安装开始时间排序，开始时间相等的按照截至时间排序
        Arrays.sort(startEnd , (o1 ,o2) -> {
            return o1[0] ==  o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
        });
        // 保存每一个时间段的终止时间，从小到大
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0 ; i < n ; i++){
            // 若当前时间段的开始时间大于了队首的终止时间，那么队首的主持人可以继续主持这个，不用加人
            if(!queue.isEmpty() && queue.peek() <= startEnd[i][0]){
                queue.poll();
            }
            queue.offer(startEnd[i][1]);
        }
        return queue.size();
    }

    public static void main(String[] args) {
        System.out.println(new NC147().minmumNumberOfHost(3, new int[][]{
                {1, 5}, {3, 4}, {5, 7}
        }));
    }
}

